package com.yequan.leetcode.sort;

/**
 * @author yequan
 * @date 2021/10/19 00:03
 **/
public class FindMedia {

    public static void main(String[] args) {
        int[] data1 = {2, 5, 4, 9, 3, 6, 8, 7, 1, 10};
        int[] data2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        FindMedia2 findMedia = new FindMedia2();
        int media = findMedia.findMediaMethod(data1);
        System.out.println(media);
    }

    static class FindMedia1 {
        public int findMediaMethod(int[] data) {
            if (null == data || data.length < 1) {
                return -1;
            }
            int mid = (data.length - 1) / 2;
            int pivotIndex = partition(data, 0, data.length - 1);
            while (true) {
                if (pivotIndex == mid) {
                    break;
                } else if (pivotIndex < mid) {
                    pivotIndex = partition(data, pivotIndex + 1, data.length - 1);
                } else {
                    pivotIndex = partition(data, 0, pivotIndex - 1);
                }
            }
            return data[pivotIndex];
        }

        private int partition(int[] data, int left, int right) {
            int pivot = data[left];
            int i = left, j = right;
            while (i != j) {
                while (i < j && data[j] > pivot) {
                    j--;
                }
                while (i < j && data[i] <= pivot) {
                    i++;
                }
                if (i < j) {
                    swap(data, i, j);
                }
            }
            data[left] = data[j];
            data[j] = pivot;
            return j;
        }

        private void swap(int[] data, int i, int j) {
            int temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }

    static class FindMedia2 {

        public int findMediaMethod(int[] data) {
            if (data == null || data.length == 0) {
                return -1;
            }
            int mid = (data.length - 1) >> 1;
            int left = 0;
            int right = data.length - 1;
            int pivotIndex = partition(data, 0, right);
            while (true) {
                if (mid == pivotIndex) {
                    break;
                }
                if (mid < pivotIndex) {
                    //如果中位数的位置小于pivotIndex, 则在左子树
                    pivotIndex = partition(data, left, pivotIndex - 1);
                } else {
                    //如果中位数的位置大于pivotIndex, 则在右子树
                    pivotIndex = partition(data, pivotIndex + 1, right);
                }
            }
            return data[pivotIndex];
        }

        private int partition(int[] data, int left, int right) {
            int pivot = data[left];
            int i = left;
            int j = right;
            while (i != j) {
                while (data[j] > pivot && i < j) {
                    j--;
                }
                while (data[i] <= pivot && i < j) {
                    i++;
                }
                if (i < j) {
                    swap(data, i, j);
                }
            }
            data[left] = data[j];
            data[j] = pivot;
            return j;
        }

        private void swap(int[] data, int i, int j) {
            int temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }


    }


}
